package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 102. 二叉树的层序遍历
 * https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * 示例 2：
 *
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 *
 * 输入：root = []
 * 输出：[]
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [0, 2000] 内
 * -1000 <= Node.val <= 1000
 */
public class Problem102 {
    public static void main(String[] args) {
        Integer[] ints=new Integer[]{3,9,20,null,null,15,7};
        TreeNode instanceNew = TreeNode.getInstanceNew(ints);

        Problem102 problem102 = new Problem102();
        List<List<Integer>> lists = problem102.levelOrder(instanceNew);
        System.out.println(lists);
    }

    /**
     * 思路:
     * 使用任意一种遍历
     * 在递归时, 除了节点本身的值外, 同时记录level作为参数. 将之放到一个resultList中
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        preOrder(root,0);
        return resultList;
    }

    private List<List<Integer>> resultList=new ArrayList<>();
    private void preOrder(TreeNode treeNode,int level){
        if(treeNode==null){
            return;
        }
        if(resultList.size()==level){
            List<Integer> tmpList=new ArrayList<>();
            tmpList.add(treeNode.val);
            resultList.add(tmpList);
        }else{
            List<Integer> tmpList = resultList.get(level);
            tmpList.add(treeNode.val);
        }

        preOrder(treeNode.left,level+1);
        preOrder(treeNode.right,level+1);
    }
}
